// https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/
// Created by ade on 2022/10/10.
//
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    // nums1 = [1,3,5,4],
    // nums2 = [1,2,3,7]
    int minSwap(vector<int> &nums1, vector<int> &nums2) {
        int len = nums1.size();
        vector <vector<int>> dp(len, vector<int>(2));
        dp[0][0] = 0; // 不交换
        dp[0][1] = 1; // 交换
        for (int i = 1; i < len; i++) dp[i][0] = dp[i][1] = len;

        for (int i = 1; i < len; i++) {
            // 交换0次 和 交换2次
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                // 严格递增
                dp[i][0] = dp[i - 1][0]; // 当前位置和前一个位置都【不交换】
                dp[i][1] = dp[i - 1][1] + 1; // 当前位置和前一个位置都【交换】
            }
            // 交换1次,要么是前面一个交换 要么是当前位置交换
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                dp[i][0] = min(dp[i][0], dp[i - 1][1]);// 前一个位置交换
                dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1); // 当前位置交换
            }
        }

        return min(dp[len - 1][0], dp[len - 1][1]);
    }
};

int main() {
    vector<int> nums1 = {3, 3, 8, 9, 10};
    vector<int> nums2 = {1, 7, 4, 6, 8};
    Solution so;
    cout << so.minSwap(nums1, nums2);
    return 0;
}